#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <list>

using namespace std;

struct vertex{
	explicit vertex(char c):ch(c){};
	char ch;
	list<vertex*> adj_vertex;
};

typedef vector<vertex> Graph;

vertex* find_v(Graph& g, char c){
	for(unsigned int i=0;i<g.size();++i)
		if(g[i].ch == c)
			return &g[i];
	return NULL;
}

void add_edge(Graph& g, char v1, char v2){
	find_v(g,v1)->adj_vertex.push_back(find_v(g,v2));
}


bool top_sort(Graph& g, vector<char>& output){
	map<char, int> indegrees;
	for(Graph::iterator i=g.begin(); i!= g.end(); ++i){
		indegrees[i->ch]=0;
	}

	for(Graph::iterator i=g.begin(); i!= g.end(); ++i){
		for(list<vertex*>::iterator j=i->adj_vertex.begin(); j!=i->adj_vertex.end(); ++j){
			indegrees[(*j)->ch] += 1;
		}
	}


	map<char,int>::iterator zi;
	while(1){
		zi = indegrees.end();
		for(map<char,int>::iterator i=indegrees.begin();i!=indegrees.end();++i){
			if(i->second == 0){
				zi=i;
				break;
			}
		}
		if(zi!=indegrees.end()){			
			output.push_back(zi->first);
			list<vertex*> & adj = find_v(g,zi->first)->adj_vertex;
			for(list<vertex*>::iterator j=adj.begin(); j!= adj.end(); ++j){
				indegrees[(*j)->ch]--;
			}
			indegrees.erase(zi);
		}else{
			break;
		}
	}
	return indegrees.empty();
}


int main(){
	map<char,string> data;
	data['a']= string("bcd");
	data['b']=string("de");
	data['c'] = string("f");
	data['d']=string("cfg");
	data['e']=string("dg");
	data['f']=string("");
	data['g']=string("f");

	Graph g;
	map<char,string>::iterator iter;   
	for( iter = data.begin(); iter != data.end(); iter++ ) {
		g.push_back(vertex(iter->first));
	}

	for( iter = data.begin(); iter != data.end(); iter++ ) {
		string str=iter->second;
		for(unsigned int i=0; i<str.size(); i++){
			add_edge(g,iter->first,str[i]);
			//		cout<<"adding edge "<<iter->first<<" "<<str[i]<<endl;
		}
	}

	vector<char> top_sort_vertex;
	if( top_sort(g,top_sort_vertex)){
		for(unsigned int i=0;i<top_sort_vertex.size();++i)
			cout<<top_sort_vertex[i]<<endl;
	}else{
		cout<<"circle detected"<<endl;
	}

	return 0;
}
